from blocks import *
import re
import sys


# return True if register is overwritten in consecutive statements
# return False if register not overwritten! 
def overwritten(blok, reg):

    for el in blok:
        if reg in el:
            t = re.split(r'[\t ,]', el)
            if reg in t:
#                print "reg",reg,"t",t,"ind",t.index(reg),"bool",t.index(reg) >= 2
                if (t.index(reg) == 2):
                    return True
                else:
                    return False
    return False    

def copy_propagation(bloc):
    instr = bloc.instructions
    for index, elem in enumerate(instr):
        if index < len(instr)-1:
            # examine sw followed by lw

            if "sw" in elem:
                el = instr[index+1]
                if "lw" in el:
                    s3 = elem.split("\t")
                    l3 = el.split("\t")
                    if s3[-1] == l3[-1]:
                        # remove load word
#                        print "=="
#                        bloc.instructions.remove(el)
                        del block.instructions[index+1]

            # examine sb followed by lb
            elif "sb" in elem:
                el = instr[index+1]
                if "lb" in el:
                    s3 = elem.split("\t")
                    l3 = el.split("\t")
                    if s3[-1] == l3[-1]:
                        # remove load word
#                        print "==2"
#                        bloc.instructions.remove(el)
                        del block.instructions[index+1]

            # examine move followed by sw
            elif "move" in elem:
                el = instr[index+1]
                if ("sw" in el) or ("sb" in el):
                    m = re.split(r'[\t ,]', elem)
                    s = re.split(r'[\t ,]', el)
                    if m[2] == s[2]:
#                        print "move"
                        instr[index+1] = el.replace(s[2], m[3])
#                        bloc.instructions.remove(elem)
                        del block.instructions[index]


    for index, elem in enumerate(instr):
        if index < len(instr)-1:
            el = instr[index+1]
            # examine subu, addu, lw, lb followed by move
            if (("lw" in elem) or ("sra" in elem) or ("lb" in elem) or ("addu" in elem) or ("subu" in elem)):
                if ("move" in el):
                    sal = re.split(r'[\t ,]', elem)
                    m = re.split(r'[\t ,]', el)
#                    print "sal",sal,"\t",elem
#                    print "m",m,"\tel",el
                    if (m[3] == sal[2]):
                        if (overwritten(instr[index+2:], sal[2])):
#                            print "if\n", m[3], sal[2]
                            instr[index] = elem.replace(sal[2], m[2],1)
#                            print "removed",instr[index+1]                        
#                            print "instr",instr[index]
                            del block.instructions[index+1]


    return bloc




def common_subexpression(blok):
    instr = blok.instructions
    for index, elem in enumerate(instr):
        if index < len(instr)-4:
            if (("lw" in elem) and ("sll" in instr[index+1]) and ("lw" in instr[index+2]) and ("addu" in instr[index+3])):
                a = elem
                b = instr[index+1]
                c = instr[index+2]
                d = instr[index+3]
                a1 = re.split(r'[\t ,]', elem)
                c1 = re.split(r'[\t ,]', c)
                y = instr[index+4]
                for x, e in enumerate(instr[index+4:]):
#                    print "xe",e
                    if (("lw" in e) and ("sll" in instr[x+1]) and ("lw" in instr[x+2]) and ("addu" in instr[x+3])):
                        if (a == e) and (c1[-1] in instr[x+2]): # (a1[-1] in e)
                            f = instr[x+1]
                            g = instr[x+2]
                            h = instr[x+3]
                            if b == f: # sll 
                                print "\na",a
                                print "b",b
                                print "c",c
                                print "d",d
                                print "y",y
                                print "\ne",e
                                print "f",instr[x+1]
                                print "g",instr[x+2]
                                print "h",instr[x+3]
                                print "i",instr[x+6]
#                print "+==============================================="
    return blok


def constant_folding(bloc):
    instr = bloc.instructions
    for index, elem in enumerate(instr):
#		print "for",elem
        if "li" in elem:
            # get constant and register ,temp[1] is register
            temp = re.split(r'[\t ,]', elem)
            if index < len(instr)-1:
                e = instr[index+1]

                # check if register (temp[1]) is used in the next lines
                if ("bne" in e) or ("beq" in e):
                    t = re.split(r'[\t ,]', e)    
                    if temp[2] in t[2]:
#                        print "if ##"
                        instr[index+1] = e.replace(t[2], temp[3])
                        bloc.instructions.remove(elem)
                    elif temp[2] in t[3]:
#                        print "el ##"
                        instr[index+1] = e.replace(t[3], temp[3])
                        bloc.instructions.remove(elem)
                elif "addu" in e:
                    t = re.split(r'[\t ,]', e)
#                    print "addu",t,"temp",temp

                    if temp[2] in t[3]:
#                        print "if ##"
                        instr[index+1] = e.replace(t[3], temp[3])
                        bloc.instructions.remove(elem)
                    elif temp[2] in t[4]:
#                        print "el ##"
                        instr[index+1] = e.replace(t[4], temp[3])
                        bloc.instructions.remove(elem)
    return bloc



if __name__ == "__main__":
    global all_blocks

    if len(sys.argv) == 3:
        input_file = sys.argv[1]
        output_file = sys.argv[2]            
    else: 
        print "usage: python block_optimization.o benchmark.s output.s"
        exit(1)

    # imported from blocks.py
    first_phase(input_file)

    f = open(output_file, "w")

    for index, block in enumerate(all_blocks):
        if index == 0:
            # write compiler directives to file
            for k in block.instructions:
                f.write(k+"\n")
        else:
            l_before = len(block.instructions)
            block = constant_folding(block)
            block = copy_propagation(block)
            block = common_subexpression(block)

            for line in block.instructions:
                f.write(line+"\n")

            l_after = len(block.instructions)
    f.close()







